package com.zs.letcode.path_problems_in_dynamic_programming;

import java.util.Arrays;

/**
 * 1575. 统计所有可行路径
 * 给你一个 互不相同的整数数组，其中locations[i]表示第i个城市的位置。同时给你start，finish和fuel分别表示出发城市、目的地城市和你初始拥有的汽油总量
 * <p>
 * 每一步中，如果你在城市 i，你可以选择任意一个城市 j，满足 j != i且0 <= j < locations.length，并移动到城市j。从城市i移动到j消耗的汽油量为|locations[i] - locations[j]|，|x|表示x的绝对值。
 * <p>
 * 请注意，fuel任何时刻都不能为负，且你可以经过任意城市超过一次（包括start和finish）。
 * <p>
 * 请你返回从start到finish所有可能路径的数目。
 * <p>
 * 由于答案可能很大， 请将它对10^9 + 7取余后返回。
 * <p>
 * 示例 1：
 * <p>
 * 输入：locations = [2,3,6,8,4], start = 1, finish = 3, fuel = 5
 * 输出：4
 * 解释：以下为所有可能路径，每一条都用了 5 单位的汽油：
 * 1 -> 3
 * 1 -> 2 -> 3
 * 1 -> 4 -> 3
 * 1 -> 4 -> 2 -> 3
 * 示例 2：
 * <p>
 * 输入：locations = [4,3,1], start = 1, finish = 0, fuel = 6
 * 输出：5
 * 解释：以下为所有可能的路径：
 * 1 -> 0，使用汽油量为 fuel = 1
 * 1 -> 2 -> 0，使用汽油量为 fuel = 5
 * 1 -> 2 -> 1 -> 0，使用汽油量为 fuel = 5
 * 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 3
 * 1 -> 0 -> 1 -> 0 -> 1 -> 0，使用汽油量为 fuel = 5
 * 示例 3：
 * <p>
 * 输入：locations = [5,2,1], start = 0, finish = 2, fuel = 3
 * 输出：0
 * 解释：没有办法只用 3 单位的汽油从 0 到达 2 。因为最短路径需要 4 单位的汽油。
 * 示例 4 ：
 * <p>
 * 输入：locations = [2,1,5], start = 0, finish = 0, fuel = 3
 * 输出：2
 * 解释：总共有两条可行路径，0 和 0 -> 1 -> 0 。
 * 示例 5：
 * <p>
 * 输入：locations = [1,2,3], start = 0, finish = 2, fuel = 40
 * 输出：615088286
 * 解释：路径总数为 2615088300 。将结果对 10^9 + 7 取余，得到 615088286 。
 * <p>
 * <p>
 * 提示：
 * <p>
 * 2 <= locations.length <= 100
 * 1 <= locations[i] <= 10^9
 * 所有locations中的整数 互不相同。
 * 0 <= start, finish <locations.length
 * 1 <= fuel <= 200
 * 相关标签
 * 记忆化搜索
 * 数组
 * 动态规划
 * <p>
 * 作者：宫水三叶
 * 链接：https://leetcode-cn.com/leetbook/read/path-problems-in-dynamic-programming/r8pzo1/
 * 来源：力扣（LeetCode）
 * 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
 *
 * @author madison
 * @description
 * @date 2021/11/2 12:46
 */
public class Chapter7 {
    public static void main(String[] args) {

    }

    private class Solution {

        int mod = 1000000007;
        // 缓存器：用于记录「特定状态」下的结果
        // cache[i][fuel] 代表从位置 i 出发，当前剩余的油量为 fuel 的前提下，到达目标位置的「路径数量」
        int[][] cache;

        /**
         * 记忆化搜索
         *
         * @param locations
         * @param start
         * @param finish
         * @param fuel
         * @return 3
         */
        public int countRoutes(int[] locations, int start, int finish, int fuel) {
            int n = locations.length;
            // 初始化缓存器
            // 之所以要初始化为 -1
            // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
            cache = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(cache[i], -1);
            }
            return dfs(locations, start, finish, fuel);
        }

        /**
         * 计算「路径数量」
         *
         * @param ls   入参 locations
         * @param u    当前所在位置（ls 的下标）
         * @param end  目标哦位置（ls 的下标）
         * @param fuel 剩余油量
         * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
         */
        private int dfs(int[] ls, int u, int end, int fuel) {
            // 如果缓存器中已经有答案，直接返回
            if (cache[u][fuel] != -1) {
                return cache[u][fuel];
            }
            int n = ls.length;
            // base case 1：如果油量为 0，且不在目标位置
            // 将结果 0 写入缓存器并返回
            if (fuel == 0 && u != end) {
                cache[u][fuel] = 0;
                return 0;
            }

            // base case 2：油量不为 0，且无法到达任何位置
            // 将结果 0 写入缓存器并返回
            boolean hasNext = false;
            for (int i = 0; i < n; i++) {
                if (i != u) {
                    int need = Math.abs(ls[u] - ls[i]);
                    if (fuel >= need) {
                        hasNext = true;
                        break;
                    }
                }
            }
            if (fuel != 0 && !hasNext) {
                cache[u][fuel] = u == end ? 1 : 0;
                return cache[u][fuel];
            }

            // 计算油量为 fuel，从位置 u 到 end 的路径数量
            // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
            int sum = u == end ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != u) {
                    int need = Math.abs(ls[i] - ls[u]);
                    if (fuel >= need) {
                        sum += dfs(ls, i, end, fuel - need);
                        sum %= mod;
                    }
                }
            }
            cache[u][fuel] = sum;
            return sum;
        }

        /**
         * 简化 Base Case（挖掘性质）
         */
        public int countRoutes1(int[] ls, int start, int end, int fuel) {
            int n = ls.length;

            // 初始化缓存器
            // 之所以要初始化为 -1
            // 是为了区分「某个状态下路径数量为 0」和「某个状态尚未没计算过」两种情况
            cache = new int[n][fuel + 1];
            for (int i = 0; i < n; i++) {
                Arrays.fill(cache[i], -1);
            }

            return dfs1(ls, start, end, fuel);
        }

        /**
         * 计算「路径数量」
         *
         * @param ls   入参 locations
         * @param u    当前所在位置（ls 的下标）
         * @param end  目标哦位置（ls 的下标）
         * @param fuel 剩余油量
         * @return 在位置 u 出发，油量为 fuel 的前提下，到达 end 的「路径数量」
         */
        private int dfs1(int[] ls, int u, int end, int fuel) {
            // 如果缓存中已经有答案，直接返回
            if (cache[u][fuel] != -1) {
                return cache[u][fuel];
            }

            // 如果一步到达不了，说明从位置 u 不能到达 end 位置
            // 将结果 0 写入缓存器并返回
            int need = Math.abs(ls[u] - ls[end]);
            if (need > fuel) {
                cache[u][fuel] = 0;
                return 0;
            }

            int n = ls.length;
            // 计算油量为 fuel，从位置 u 到 end 的路径数量
            // 由于每个点都可以经过多次，如果 u = end，那么本身就算一条路径
            int sum = u == end ? 1 : 0;
            for (int i = 0; i < n; i++) {
                if (i != u) {
                    need = Math.abs(ls[i] - ls[u]);
                    if (fuel >= need) {
                        sum += dfs1(ls, i, end, fuel - need);
                        sum %= mod;
                    }
                }
            }
            cache[u][fuel] = sum;
            return sum;
        }
    }
}
